/**
 * @param {string} s
 * @return {string[]}
 */
var restoreIpAddresses = function(s) {
    if(s.length > 12 || s.length < 4) return []
    // 在第i个位置插入 “.”
    const res = []
    let path = []
    const dfs = function(start) {
        if(path.length > 4) return
        if(path.length === 4 && start === s.length) {
            res.push(path.join('.'))
            return
        }
        // 剪枝，如果添加了4个，但是还没耗尽，直接返回
        if(path.length === 4 && start < s.length) return
        for(let i = start + 1; i <= start + 3; i++) {
            if(!isValid(s.substring(start, i))) continue
            path.push(s.substring(start, i))
            dfs(i)
            path.pop()
        }
    }
    dfs(0)
    return res
};
function isValid(str) {
    if(str.length > 1 && str[0] === "0") return false
    if(str.length <= 1) return true
    if(str[0] !== 0 && parseInt(str) >= 0 && parseInt(str) <= 255) return true
    return false
}
console.log(restoreIpAddresses("25525511135"));